package DivideyVenceras;
import java.util.Scanner;

public class Principal {
	
	public static void main(String [] args){
		int num,edad;
		long ti,tf;
		Scanner leer= new Scanner(System.in);
		System.out.println("Introduzca el numero de solados para N");
		num=leer.nextInt();
		int [] n = new int [num];
		n=Cosas.aleatorizar(num,n);
		System.out.println("Introduzca el numero de solados para M");
		num=leer.nextInt();
		int [] m=new int [num];
		m=Cosas.aleatorizar(num,m);
		Cosas.quicksort(n,0,n.length-1);
		Cosas.quicksort(m,0,m.length-1);
		System.out.println("La fila de soldados N es:");
		for (int i=0;i<n.length;i++)
			System.out.print(n[i]+" ");
		System.out.println("\nLa fila de soldados M es:");
		for (int i=0;i<m.length;i++)
			System.out.print(m[i]+" ");
		ti=System.nanoTime();
		edad=Nieve(n,m);
		tf=System.nanoTime()-ti;
		System.out.print("\nLa edad de Jhon Nieve es "+edad+" y se ha procesado en "+tf+" Nanosegundos");
	}

	//Principales
	public static int Nieve(int [] N, int [] M){
		int [] a,b;
		int edad;
		
		if (N.length>M.length){
			a=M;
			b=N;	
		}
		else {
			a=N;
			b=M;
		}
		if(a.length<2)
			edad=casobase1(a,b);
		else
			edad=casogeneral(a,0,a.length-1,b,0,b.length-1);
		return edad;
	}
	public static int casobase1(int [] a,int [] b){
		int result = 0;
		if(a.length==0 || b.length==1)
			result=b[b.length/2];
		else
			if(b.length%2!=0)
				result=b[b.length/2];
			else
				if(a[0]>b[b.length/2])
					result=b[b.length/2];	
				else
					if(b.length==2){
						if(a[0]>b[(b.length/2)])
							result=b[(b.length/2)-1];
						else 
							result=a[0];
					}
		
					else
						if(a[0]>b[(b.length/2)-1])
							result=b[(b.length/2)-1];
						else 
							result=a[0];
		return result;
		
	}
	public static int casogeneral(int [] a, int liA,int lsA,int [] b, int liB, int lsB){
		int ma,mb;
		int result = 0;
		ma=(liA+lsA)/2;
		mb=(liB+lsB)/2;
		if(a[ma]==b[mb]){
			result=b[mb];
		}
		else{
			if(lsA-liA==1){
				result=casobase2(a,liA,lsA,ma,b,liB,lsB,mb);
			}
			else{
				if(a[ma]<b[mb]){
					liA=ma;
					lsB=b.length-ma-1;
					result=casogeneral(a,liA,lsA,b,liB,lsB);
				}
				else {
					lsA=ma;
					liB=a.length-ma-1;
					result=casogeneral(a,liA,lsA,b,liB,lsB);
				}
			}
		}
		
		return result;
	}
	public static int casobase2(int [] a, int liA,int lsA,int ma,int [] b, int liB, int lsB,int mb){
		int result=0;
		if(b[mb]>=a[lsA] && mb>0){
			if(b[mb-1]>a[lsA]){
				result=b[mb-1];
			}
			else{
				result=a[lsA];
			}		
		}
		else{
			if(b[mb]>a[liA]){
				result=b[mb];
			}
			else{
				if(b[mb+1]>a[liA]){
					result=a[liA];
				}
				else{
					result=b[mb+1];
				}
			}
		}
			
		return result;
	}
}
